1. Field of the Invention
The present invention generally relates to the art of digital computer systems, and more specifically to a method and structure for interrupt polling signal bandwidth allocation in a universal serial bus system.
2. Description of the Related Art
Digital Personal Computers (PC) have been conventionally provided with a number of connectors for connection to peripheral units, such as a monitor, keyboard, mouse, printer, modem, etc. Until recently, the connectors have had a variety of configurations, including number of pins, shape, and interface type (e.g. serial, parallel). This unnecessarily increases the complexity and cost of the computer system, since the computer must be able to accommodate and integrate the different interface and connector types.
A conventional PC serial bus is limited to a data transfer rate of approximately 115 kilobits/sec. This is far below the speed which is required by new expansion options such as telephony, multimedia, and high speed storage devices.
A standard called "Plug and Play" has been introduced which is intended to automatically identify and configure peripheral components such as modems, sound cards, etc. that are plugged into a computer via internal slots. This expedient is limited to internal components, and cannot be extended to external peripherals such as printers.
In addition, Plug and Play systems often fail to identify components, or identify them incorrectly, causing a system configuration problem which is more complicated to deal with than the manual configuration procedure which Plug and Play is intended to eliminate.
A new system has emerged which overcomes the drawbacks of the conventional multi-interface arrangement, as well as Plug and Play. The system is entitled "Universal Serial Bus (USB)", and is implemented by a register level interface standard entitled "Open Host Controller Interface (OHCI)" which is being developed by a consortium of computer industry manufacturers. The system is a bus having a unitary interface type, and the same physical connectors at all levels.
Another host controller system has been introduced by Intel, which is entitled "Universal Host Controller Interface (UHCI)".
USB enables a wide variety of peripherals to be connected through a single physical connector at the back of PC, thereby replacing the multiple ports which are currently required. This is accomplished by having several peripheral units connected to one another in a tree-like configuration.
A hub is an intelligent wiring connector that connects to the PC (or to another hub upstream), and provides attachment for additional peripheral units.
USB enables bi-directional isochronous and asynchronous transfer rates of up to 12 megabits/sec over the same set of wires, making it possible for a single PC controller to link up with up to 63 digital peripherals such as a mouse, modem, speaker, joystick, laptop or handheld computer, telephone system, headset, etc.
The USB system provides for automatic identification and configuration of compatible external as well as internal peripheral units, thereby overcoming the limitations of Plug and Play. When a peripheral is added to the system (this can occur "hot" while the system is up and operating), it is identified and automatically added to a data structure which is maintained by the controller software. The data structure identifies the unit by a unique identifier code, and includes entries for communicating with the unit in accordance with its individual requirements.
The data structure includes data specifying four types of data transfers which can be performed between the controller and the peripheral units: interrupt transfers, isochronous transfers, control transfers, and bulk transfers.
Interrupt transfers, to which the present invention relates, are implemented by periodically polling the peripheral units at intervals which depend on the individual requirements. In response to being polled, a peripheral unit returns data to the controller representing the result of performing a specific action, e.g. the result of a keyboard key press. The controller passes the data from the peripheral unit to the PC memory for suitable processing.
Different types of peripheral units have different polling interval requirements. In the OHCI system, polling intervals are defined relative to a series of 32 "frames", each of which has a fixed period of 1 millisecond. A peripheral unit can be polled every millisecond, or at power-of-two multiples of 1 millisecond. The UHCI system can use any power of two, although it is practically limited to 1,024 ms.
The data specifying the polling structure for the peripheral units is stored in a polling list which is arranged in a binary tree configuration. The tree has nodes which are arranged at levels that correspond to powers of two. Data for peripheral units which must be polled every millisecond is located at the root node of the tree; data for peripheral units which must be polled every two milliseconds is stored in the first predecessor level from the root node, etc.
The data for each peripheral unit has a certain "bandwidth", which can be specified as bytes of data, percentages of a frame period, etc. For example, one peripheral unit may require transfer of 10 bytes of data upon being polled, another peripheral unit may require 5 bytes, another may require 25 bytes, etc.
The USB system itself has an inherent bandwidth limitation in that the time (bandwidth) required to transfer all data within each frame cannot exceed the frame period of 1 millisecond. In addition, it is desirable to allocate the bandwidths to the multiple paths of the tree structure such that the paths have approximately equal bandwidths.
An implementation of the USB standard is described in a publication entitled "Open HCI Open Host Controller Interface Specification for USB, Compaq, Microsoft, National Semiconductor, Jan. 22, 1997 2:28 PM Release:1.0a". Section 5.2.7.2.1 of this document presents a method for allocating newly added peripheral units to nodes in the polling list, and thereby allocating bandwidths to the paths of the tree structure.
The method uses a "brute force" approach, which involves calculating the maximum bandwidth for every path in the tree from the input or leaf nodes through the root node, and adding a new peripheral unit to the node of the required level which has the lowest calculated bandwidth.
This method is inefficient in that it requires an unnecessarily large amount of calculation, translating into an unnecessarily large amount of time for which the system is unavailable for performing other tasks.